package com.base.weeks.weekof271th;

import java.util.Stack;

/**
 * TODO
 *
 * @author leon
 * @date 2021年12月12日 11:20
 */
public class SubArrayRanges {

    public long subArrayRanges(int[] nums) {
        long res = 0L;
        Stack<Integer> maxStack = new Stack<>();
        Stack<Integer> minStack = new Stack<>();
        // 起点
        for (int i = 0; i < nums.length; i++) {
            maxStack.push(nums[i]);
            minStack.push(nums[i]);
            // 终点
            for (int j = i + 1; j < nums.length; j++) {
                int min = minStack.peek();
                int max = maxStack.peek();
                maxStack.push(Math.max(max, nums[j]));

                minStack.push(Math.min(min, nums[j]));
                res += Math.abs(maxStack.peek()-minStack.peek());

            }
            minStack.clear();
            maxStack.clear();
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new SubArrayRanges().subArrayRanges(new int[]{4,-2,-3,4,1}));
    }
}
